package newcoder_exp.justPractise;
import java.util.*;
import java.util.stream.Collectors;
//使用并查集解决

import org.junit.Test;
public class NC95 {

    public int longestConsecutive(int[] nums) {
        int len;
        if (nums == null || (len = nums.length) == 0) return 0;
        Set<Integer> set = Arrays.stream(nums).boxed().collect(Collectors.toSet());
        UnionFindSet ufs = new UnionFindSet(set);
        int res = 1;
        for (int n: set) {
            if (set.contains(n + 1)) {
                int t = ufs.union(n, n + 1);
                res = Math.max(t, res);
            }
        }
        return res;
    }

    @Test
    public void test() {
        int[] nums = {1,1,1,2,2,3};
        int res = longestConsecutive(nums);
        System.out.println(res);
    }
}

class UnionFindSet {
    Map<Integer, Integer> parent;
    Map<Integer, Integer> weight;

    public UnionFindSet(Set<Integer> nums) {
        parent = new HashMap<>();
        weight = new HashMap<>();

        for (int n : nums) {
            parent.put(n, n);
            weight.put(n, 1);
        }
    }

    //查找当前节点的祖先节点
    public int find(int n) {
        if (parent.get(n) == n) {
            return n;
        }

        int p = parent.get(n);
        int res = find(p);
        //路径压缩
        parent.put(n, res);
        return res;
    }

    public int union(int n1, int n2) {
        int r1 = find(n1), r2 = find(n2);
        int res;
        if (r1 == r2) return weight.get(r1);
        else if (r1 < r2) {
            parent.put(r2, r1);
        } else {
            parent.put(r1, r2);
        }
        res = weight.get(r1) + weight.get(r2);
        weight.put(r1, res);
        weight.put(r2, res);
        return res;
    }
}